Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. Cloud computing providers may offer infrastructure as a service (IaaS), platform as a service (PaaS), storage as a service (SaaS), data as a service (DaaS), etc. Each of these services typically has the properties of elasticity (ability to deal with new nodes being added and existing nodes being removed dynamically), high availability, scalability, and linear response times.
One or more of IaaS, PaaS, SaaS and DaaS may be used to implement a distributed data store such as a distributed database. In a distributed data store, data may be distributed across multiple different data stores. Such data may periodically be moved to balance load, reduce costs, and/or for other reasons. Additionally, new data stores may be brought online or existing data stores may be taken offline dynamically. Therefore, clients do not typically know where particular data items reside in the distributed data store. To access data, clients usually need to contact a name server that maintains information that shows which particular data store in the distributed data store each item of data is stored on at any given time. However, since clients typically need to contact the name server, the name server may become a bottleneck that can reduce throughput for the distributed data store.